The invention relates to creation of video sequences. Human artists now usually synthesize these video sequences. They laboriously create individual frames, each of which is slightly different from the preceding so as to simulate movement of the objects in the frames when the sequence is displayed.
After a series of frames are complete, the creator views them to assure realism. Quite often, defects exist, so the creator then edits the frames and continues this iterative process until a satisfactory final version exists.
To view a video sequence, the individual frames of a video sequence must go through a mathematical processing called rendering. Rendering converts the human-generated frames into images suitable for viewing. Rendering is very computation-intensive, requiring an enormous number of individual calculations. Recent improvements in the algorithms have allowed the use of parallel processing that greatly reduce the rendering time for a video sequence.
The rendering computations now commonly used do not always produce accurate images however. One particular area of inaccuracy involves the display of objects at different distances from the observer, and which are illuminated from one or more sources. Frequently, the rendering will provide images that do not provide life-like representations of such illuminations and partial obscuring of objects, with shadows and lighted areas not accurately depicted. Partially lit areas will appear too dark or too bright. Such inaccuracies are conventionally referred to as aliasing.
Shadow map calculations are widely used to generate shadows in computer-generated images. Unlike a color image comprised of a two-dimensional array of color values, a shadow map comprises a two-dimensional array of depth values. For this reason, shadow maps cannot be filtered in the same way as color images. This typically leads to inaccuracy in the way that objects at different distances from the observer and from the light sources appear to the observer, i.e., aliasing.
The initial approach to reduced aliasing in shadow maps was a method known as percentage-closer filtering as for example is taught in “Rendering Antialiased Shadows with Depth Maps”, Reeves, W., D. Salesin, and R. Cook, Computer Graphics, vol. 21, 1987, p. 283-291. Practitioners know this method well. It is commonly used in modern rendering systems, including high-performance graphics accelerators.
Essentially, each pixel in a depth map represents a step function, and the step in the step function occurs at the depth value stored for the pixel in the depth map. The result of the step function is binary, i.e., lookups into the depth map produce, for each pixel, a result that is either 0 (completely in shadow) or 1 (completely illuminated). Percentage-closer filtering examines the lookup results of a region of pixels in the depth map and weights them according to a weighting function. The weighted results are then summed into a single value in the range [0,1] which represents a weighted estimate of the ratio of pixels in the examined region which are not in shadow.
One of the primary disadvantages of the percentage-closer filtering method is it often requires exceedingly high-resolution shadow maps and large filter regions in order to produce high-quality results. This is especially true when rendering scenes comprised of finely detailed objects, such as hair or fur. In this case, a very large region of pixels must be examined by the percentage-closer filtering method in order to return good anti-aliasing results. The use of such large filter regions can be computationally expensive. Even worse, the total number of pixels in the shadow map must be increased to accommodate the large filtering regions. This often requires the size of the shadow map to be increased exponentially, which likewise causes an exponential increase in storage requirements.
To remedy these problems, at least one system uses deep shadow maps as a further improvement to the percentage-closer filtering method. Instead of storing a single depth value for each pixel in a shadow map, a deep shadow map stores a visibility function at each pixel. Each visibility function is parameterized by its particular depth; therefore each pixel of a deep shadow map includes a representation of the visibility function over multiple depth values.
In U.S. Pat. No. 6,760,024, Lakovic, T. and E. Veach (2000), the representation of the visibility function is piecewise-linear, i.e., each pixel in the deep shadow map is comprised of a list of values representing a piecewise-linear approximation of the visibility function associated with the pixel. The number of elements in the list of each pixel may vary, and in some cases large quantities of elements may be present in a list. Therefore a compression algorithm may be used to reduce the size of the lists to thereby minimize memory accesses and storage space.
In this regard, lookups into a deep shadow map fail to produce for each pixel, a binary result, e.g., 0 or 1. Rather, lookups for each pixel return a fractional value in the range [0,1]. These fractional values can then be percentage-closer filtered as before. Because the lookup value for each pixel within the neighborhood is a fractional value in the range [0,1] rather than a binary value, the overall filtering which is obtained from a deep shadow map is superior to prior-art percentage-closer filtering methods.
From a technical perspective, it is somewhat inaccurate to suggest that a deep shadow map storing a visibility function for each pixel in the shadow map significantly advanced the technology. As a practical matter, the single depth value stored for each pixel in the map by earlier shadow map systems storing also represents a “visibility function,” wherein each pixel represents a step function as previously described in the discussion of percentage-closer filtering. The novelty of the Lakovic and Veach deep shadow maps, therefore, is the method of storing a piecewise-linear approximation to a visibility function that is more sophisticated than a step function. Indeed, this is the real emphasis of the Lakovic and Veach patent.
One of the primary disadvantages of the deep shadow map method is the variable nature of its storage requirements. Because each pixel in the map comprises a piecewise-linear approximation to a visibility function, and because each piecewise-linear approximation may comprise a variable number of elements depending on the particular pixel, the memory storage requirements of a deep shadow map will vary. Furthermore, elements of each pixel are typically stored in a linked-list data structure which often causes list elements to be fragmented, i.e., stored in a non-contiguous arrangement within the memory image of the shadow map, requiring extra memory access events to store and retrieve individual pixel data.
For these reasons, deep shadow maps are by nature not “friendly” to real-time hardware circuits exemplified by modern Graphics Processing Units (GPUs). Most state-of-the-art GPUs are highly optimized Single Instruction Multiple Data (SIMD) hardware machines designed to efficiently process regular or repeating patterns of data arranged or residing in contiguous chunks of memory. The deep shadow map method, by contrast, does not conform well to the requirements of SIMD processing due to its variable nature, and it has therefore been relegated in practice only to non real-time software embodiments, e.g., computer graphics rendering applications such as the RenderMan® software system.
Variance shadow maps, a recent improvement to prior-art methods, overcome some of these obstacles in a very clever way. The publication “Variance Shadow Maps,” Donnelly, W. and A. Lauritzen, Proceedings of the 2006 Symposium on Interactive 3D Graphics and Games, ACM Press, 2006, p. 161-165, introduced the original variance shadow map method. Unlike prior-art shadow maps (or deep shadow maps), a variance shadow map stores both the mean and variance values for each pixel.
The mean and variance values stored at each pixel within a variance shadow map parameterize a visibility function similar to that of a deep shadow map. The difference is that a variance shadow map, unlike a deep shadow map, does not store a piecewise-linear approximation to the visibility function. Instead, the variance shadow map stores an analytical approximation to the visibility function, which analytical approximation is parameterized (specified) by the two mean and variance values.
The mean and variance values stored for each pixel of a variance shadow map characterize the distribution of depth values within the area of the pixel. Typically, each mean and variance value is computed in a pre-processing step from a prior-art depth map, which is allocated and rendered with a higher resolution than the variance shadow map so as to provide a sub-pixel resolution. Sub-pixel resolution means that each pixel is subdivided into two or more pixels. The system generates a mean and variance pair for each sub-pixel. Thus, a number of mean and variance pairs define the appearance of each pixel.
The mean and variance of all sub-pixel areas within each pixel of a prior-art depth map can then easily be computed and stored in the associated pixel location within the variance shadow map. This data can then be translated into an improved definition of the pixel itself.
Various processes for filtering the variance shadow map data exist. Filtering of this variance shadow map data creates more realistic pictorial presentations. The details for such filtering are presented in the previously cited Donnelly and Lauritzen publication. To summarize, variance shadow maps can be pre-filtered using well-known methods such as mipmaps and summed area tables. This is not unlike the filtering that the Lakovic and Veach system performs in the deep shadow maps operations.
The major difference is that variance shadow maps conform well to the requirements of SIMD processing. This is due to the fact that each sub-pixel in a variance shadow map stores exactly the same number of mean and variance pairs. Therefore the memory requirements of the variance shadow map for each pixel are fixed, and the total memory requirements are a function of the resolution of the map. Additionally, the memory image of a variance shadow map forms a regular and repeating pattern of data easily arranged into contiguous chunks of memory. All of these properties suit SIMD processing requirements well, and for this reason SIMD processing computes variance shadow maps very efficiently. This is the major advantage of the variance shadow map system that Donnelly and Lauritzen taught. The success of the Donnelly and Lauritzen system in providing a real-time implementation using commercially-available GPUs underscores its value.
Variance shadow maps are not a panacea, however. In fact they have one significant defect. To describe this defect, Donnelly and Lauritzen used the term “light bleeding.” in their article. The defect arises in the analytical approximation used by the variance shadow mapping approach. The analytical approximations that the mean and variance pairs associated with each pixel in the variance shadow map employ form the source of difficulty.
More specifically, the analytical approximation used by the method is a mathematical formula known as the one-tailed variant of “Chebychev's inequality,” namely
                              P          ⁡                      (            z            )                          =                              σ            2                                              σ              2                        +                                          max                ⁡                                  (                                                            z                      -                      μ                                        ,                    0                                    )                                            2                                                          (        1        )            
In this formula, μ and σ2 are the mean and variance, respectively, stored at a pixel within the variance shadow map, and the variable z represents increasing depth. When a lookup is performed, the mean and variance of a pixel within the variance shadow map are used to compute P for a given depth value z. The result of computing P will be a value in the range [0,1] representing the fractional amount of illumination for the pixel.
The problem with this analytical approximation is that for any given mean and variance, the value of P is overly conservative. This means that P will generally be “too bright,” i.e., it will tend to falsely indicate that a pixel is more brightly illuminated than is true. Worse still equation (1) falsely indicates that a pixel is partially in shadow when in fact the pixel is completely shadowed. That is, light bleeds from neighboring pixels to distort the actual illumination for the pixel in question. This is a shortcoming of the Chebychev inequality, and it is the source of the unwanted light bleeding artifacts characteristic of the variance shadow map method.
FIGS. 1a and 1b show this in more detail. FIG. 1a is an example a distribution of 16 depth values defining the distance of areas in a filter region from a viewer. One can consider a filter region to correspond to a single pixel, although from a theoretical standpoint a filter region may comprise more or less than a single pixel. Larger depth values represent a greater distance of the filter region from the viewer.
The mean and variance of the 16 depth values in FIG. 1a are computed to specify a respective P value, which is depicted in FIG. 1b. The horizontal axis represents increasing distance from the viewer, e.g., increasing depth, and the vertical axis represents the fractional illumination of the entire filter region. If P(z) is 1, the region is totally illuminated; if P(z) is 0 the region is totally in shadow. Other values of P(z) in the range [0,1] indicate a fractional amount of illumination as seen by the viewer. One notes however that the actual minimum and maximum depth value within the region is, respectively, 2 and 8. Therefore all depth values smaller than 2 should be totally illuminated. Similarly, all depth values larger than 8 should be in total shadow. Intuitively speaking, a smooth transition from total illumination to total shadow in a manner which correlates to the distribution of depth values within the filter region would also be expected as an advantageous feature.
As can clearly be seen in FIG. 1, however, P does not posses any of these desirable properties. More specifically, the graph of P shows that all depth values within the filter region that are less-than or equal to 4 are completely illuminated when in fact they should be at least partially in shadow, i.e., they are “too bright.” Similarly, the transition between the range of depth values within the region, i.e., the transition between the minimum depth value 2 and the maximum depth value 8, does not correlate to the distribution of depth values within the region. Even worse, the graph of P shows that depth values greater than 8 are at least partially illuminated when in fact any depth value greater than 8 should be in total shadow, i.e., “light bleeding” occurs because no light should penetrate beyond the largest depth value within the filter region, which in this case is 8. But as can clearly be seen, P does not represent this phenomenon accurately, and it is therefore the cause of artifacts in the prior-art methods.
Several ad-hoc approaches have been proposed to artificially “darken” the shadows produced by variance shadow maps in an effort to compensate for the light bleeding artifacts, e.g., “Summed-Area Variance Shadow Maps,” Lauritzen, A., in chapter 8 of the book “GPU Gems 3,” Addison Wesley Professional, 2007. Unfortunately, such an ad-hoc approach makes it difficult to produce acceptable results in all cases since the approach is not based on any plausible or physical mathematical relationship. Even in cases where it does work, such an ad-hoc approach often produces shadows that are “too dark” and therefore look unrealistic.
Other similar approaches include “Layered Variance Shadow Maps,” Lauritzen, A., and M. McCool, 2008; “Convolution Shadow Maps,” Annen, T. et. al., Eurographics Symposium on Rendering, 2007; and “Exponential Shadow Maps,” Annen, T. et. al., Graphics Interface, 2008. All of these additional ad-hoc methods are similar variations on a theme, i.e., variance shadow maps, and, more specifically, they all attempt to address, unsuccessfully, the “light bleeding” issue previously described. As can clearly be seen by this body of work, there is a need for an improved variance shadow map method, namely a method for eliminating the “light bleeding” artifact which plagues the prior-art methods.